package tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @描述：广度/深度优先遍历算法，注意递归与循环操作的差别，以及与深度优先的区别
 * @时间：2014年12月25日 下午3:02:39
 * @作者：hongxingfan
 * 
 * @学到：递归与非递归的区别在于，递归需要应用外部容器类
 */
public class BreadthDepthFirstSearch {

	// 定义一个类似的树结构
	static class Node {
		String value;
		List<Node> nodes = new ArrayList<Node>();

		public Node(String value) {
			this.value = value;
		}

		public String getValue() {
			return value;
		}

		public void setValue(String value) {
			this.value = value;
		}

		public void addNode(Node node) {
			this.nodes.add(node);
		}

		public List<Node> getNodes() {
			return this.nodes;
		}

		public boolean hasChildren() {
			return nodes.size() > 0 ? true : false;
		}
	}

	public static void main(String[] args) {
		Node root = new Node("root");

		Node level1_1 = new Node("level1_1");
		Node level1_2 = new Node("level1_2");
		Node level1_3 = new Node("level1_3");
		Node level1_4 = new Node("level1_4");
		root.addNode(level1_1);
		root.addNode(level1_2);
		root.addNode(level1_3);
		root.addNode(level1_4);

		Node level2_1_1 = new Node("level2_1_1");
		Node level2_1_2 = new Node("level2_1_2");
		Node level2_2_1 = new Node("level2_2_1");
		Node level2_3_1 = new Node("level2_3_1");
		Node level2_3_2 = new Node("level2_3_2");
		Node level2_3_3 = new Node("level2_3_3");
		Node level2_3_4 = new Node("level2_3_4");
		level1_1.addNode(level2_1_1);
		level1_1.addNode(level2_1_2);
		level1_2.addNode(level2_2_1);
		level1_3.addNode(level2_3_1);
		level1_3.addNode(level2_3_2);
		level1_3.addNode(level2_3_3);
		level1_3.addNode(level2_3_4);

		// bFS(root);
		dFS(root);
		ddFS(root);
	}

	// 广度优先遍历，利用队列的性质
	public static void bFS(Node root) {
		Queue<Node> queue = new ArrayBlockingQueue<Node>(100);
		queue.add(root);
		while (queue.size() > 0) {
			Node node = queue.poll();
			System.out.print(node.getValue() + "-->");
			for (Node n : node.getNodes()) {
				queue.add(n);
			}
		}
		System.out.println();
	}

	// 深度优先遍历，利用栈的性质，同一级的node倒序输出
	public static void dFS(Node root) {
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		while (stack.size() > 0) {
			Node node = stack.pop();
			System.out.print(node.getValue() + "-->");
			for (Node n : node.getNodes()) {
				stack.push(n);
			}
		}
		System.out.println();
	}

	// 深度优先遍历，递归实现
	private static Set<Node> set = new HashSet<Node>();

	public static void ddFS(Node node) {
		if (node.hasChildren()) {
			if (set.add(node)) {
				System.out.print(node.getValue() + "-->");
			}
			for (Node n : node.getNodes()) {
				ddFS(n);
			}
		} else {
			if (set.add(node)) {
				System.out.print(node.getValue() + "-->");
			}
		}
	}
}
